package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	newNode := &TreeNode{Val: val}
	if root == nil {
		return newNode
	}
	if val < root.Val {
		if root.Left == nil {
			root.Left = newNode
		} else {
			insertIntoBST(root.Left, val)
		}
	} else if val > root.Val {
		if root.Right == nil {
			root.Right = newNode
		} else {
			insertIntoBST(root.Right, val)
		}
	}
	return root
}

func main() {
	root := &TreeNode{
		Val: 4,
		Left: &TreeNode{
			Val: 2,
		},
		Right: &TreeNode{
			Val: 7,
		},
	}
	root = insertIntoBST(root, 5)
	println(root)
}
